#pragma once
#include <assert.h>
#include <queue>
#include <algorithm>
#include <ostream>

using namespace std;

// Interface for classes that process input values, run them trhough a statistic and output values.
template<class TIn, class TOut> class IOnlineStatistic {
    public:
        virtual ~IOnlineStatistic() {}
        virtual void RecordInput(const TIn val) = 0;
		virtual bool HasValue() = 0;
		virtual TOut GetCurrentStatistic() = 0;
		virtual void PrintState(ostream& out) = 0;
};

// An implementation of online median.
// Ideally, this would use 2 priority queues for the 2 halves of the sorted dataset,
// plus a fifo queue to represent 'the window' and aging of elements.
// If W is the size of the window, insertion in RecordInput() would be O(log(W)) (thanks to the heap/tree
// algorithm used in pqueue) and retrieval of median in GetCurrentStatistic() be O(1).
// Amortised constant time could be achieved by adding a log(W)-wide buffer storing 'central' values,
// thus avoiding insertion in the pqueues when inserting an element close to the current median.
//
// Due to the lack of a remove() operator in STL priority queue, however, using this solution is impractical.
// The choice is thus between implementing our own data structure (e.g. pqueue based on heap, or skip list),
// or use a simpler container with a price on the performance side.
//
// Here we use a standard array, using binary search for insertion, hence achieving O(W) insertion (due to
// the need to shift elements in the array) and O(1) retrieval, made optimal with memoisation of the current median.
// We minimise the number of copied elements during insertion by shifting only those between the value
// being inserted and the one being removed.
// Stored elements are also placed in a std::queue, to maintain aging information. This is the most pratical
// choice. Performance _may_ benefit from replacing the queue with a simple array.
template<class TIn, class TOut> class OnlineMedian : public IOnlineStatistic<TIn, TOut> {
	private:
		int _currentCount;
		int _windowSize;
		TOut _currentMedian;
		int _currMedianIndex;
		TIn* _pValues;
		std::queue<TIn>* _pHistory;
		void Fill(const TIn val);
		int RemoveEldest();
		
	public:
		OnlineMedian(int windowSize, bool prefillWindow, TIn prefillValue = 0);
        virtual ~OnlineMedian();
        virtual void RecordInput(const TIn val);
		virtual inline bool HasValue();
		virtual inline TOut GetCurrentStatistic();
		virtual void PrintState(ostream& out);
};


// *** *** TEMPLATE IMPLEMENTATIONS *** *** //

template<class TIn, class TOut> OnlineMedian<TIn, TOut>::OnlineMedian(int windowSize, bool prefillWindow, const TIn prefillValue = 0) {
	if(windowSize < 1)
		throw "Invalid window size.";
	_currentCount = 0;
	_currMedianIndex = 0;
	_windowSize = windowSize;
	_pValues = new TIn[windowSize];
	_pHistory = new std::queue<TIn>();
	if(prefillWindow)
		Fill(prefillValue);
}

template<class TIn, class TOut> void OnlineMedian<TIn, TOut>::Fill(const TIn val) {
	while(_currentCount < _windowSize)
		RecordInput(val);
}

template<class TIn, class TOut> OnlineMedian<TIn, TOut>::~OnlineMedian() {
	if(_pValues != NULL) {
		delete[] _pValues;
		_pValues = NULL;
	}
	if(_pHistory != NULL) {
		delete _pHistory;
		_pHistory = NULL;
	}
}

template<class TIn, class TOut> int OnlineMedian<TIn, TOut>::RemoveEldest() {
	TIn value = _pHistory->front();
	int index = lower_bound(_pValues, _pValues + _currentCount, value) - _pValues;
	assert(index >= 0 && index < _currentCount && _pValues[index] == value);
	_pHistory->pop();
	_currentCount--;
	return index;
}

template<class TIn, class TOut> void OnlineMedian<TIn, TOut>::RecordInput(const TIn val) {
	int eldestIndex = -1;
	if(_currentCount == 0)
		_currentMedian = val;

	// Update history queue
	int previousCount = _currentCount;
	while(_currentCount >= _windowSize)
		eldestIndex = RemoveEldest();
	_pHistory->push(val);
	_currentCount++;

	// Find new element position in sorted array
	int insertionIdx = lower_bound(_pValues, _pValues+previousCount, val) - _pValues;

	// Shift elements between inserted and removed values
	if(insertionIdx != eldestIndex) {  // Save some work in that case
		if(eldestIndex >= 0) {  // Window is full
			// Shift data between eldestIndex and insertionIdx by one position
			if(eldestIndex < insertionIdx)  {    // Shift down and adjust insertionIdx
				std::copy(_pValues+eldestIndex+1, _pValues+insertionIdx, _pValues+eldestIndex);
				insertionIdx--;
			}
			else                              // Shift up
				std::copy_backward(_pValues+insertionIdx, _pValues+eldestIndex, _pValues+eldestIndex+1);
		}
		else if(insertionIdx <= previousCount-1)  // Window not full - shift up
			std::copy_backward(_pValues+insertionIdx, _pValues+previousCount, _pValues+previousCount+1);
	}

	// Store new element in sorted array
	_pValues[insertionIdx] = val;

	// Recompute median
	if((_currentCount % 2) > 0)  // Odd # of elements
		_currentMedian = _pValues[_currentCount/2];
	else  // Even # of elements -> take average of central 2
		_currentMedian = (TOut) ((_pValues[_currentCount/2] + _pValues[_currentCount/2-1]) / 2.0);
}

template<class TIn, class TOut> bool OnlineMedian<TIn, TOut>::HasValue() {
	return (_currentCount > 0);
}

template<class TIn, class TOut> TOut OnlineMedian<TIn, TOut>::GetCurrentStatistic() {
	if(!HasValue())
		throw "No recorded values.";
	return _currentMedian;
}

template<class TIn, class TOut> void OnlineMedian<TIn, TOut>::PrintState(ostream& out) {
	if(!HasValue()) {
		out << "No values." << endl;
		return;
	}
	for(int i=0; i<_currentCount-1; i++)
		out << _pValues[i] << ", ";
	out << _pValues[_currentCount-1];
	out << " -> " << _currentMedian << endl;
}